The present invention relates to methods of and apparatus for coding and decoding that are used for transmitting, recording or reproducing digital video signals and, more particularly, to variable length encoding and decoding of the digital signals.
In a known video transmission system or video recording and reproducing apparatus, such as a video tape recorder (VTR), digital signals representing a video image are compressed and encoded according to a generic coding standard, such as the JPEG standard. Typically, the digital signals are orthogonally transformed and quantized and then variable length encoded to compress the digital signals and reduce the amount of data needed to represent the video image.
As shown in FIG. 1, for example, digital signals representing a portion of a video image are supplied via input terminal 11 to a discrete cosine transform (DCT) circuit 1 which transforms the portion of the image from the time domain into the frequency domain to reduce spatial redundancy within the video image. The portion of the video image, such as a block of 8 horizontal pixels width by 8 vertical pixels height, is converted by DCT transformation from a block representing luminance or chrominance amplitudes into a block of 8 by 8 frequency coefficients to form a sequence of 64 coefficients representing respective frequencies contained in the block. The first coefficient is referred to as the DC coefficient, while the remaining 63 coefficients are referred to as the AC or high frequency coefficients. Typically, a block of pixels representing a solid portion of a video image is transformed into a DC coefficient indicating the amplitude of the solid portion and into no non-zero value AC coefficients. By contrast, a block of pixels representing a highly detailed image portion is transformed into coefficient data having many non-zero AC coefficients.
The DCT circuit 1 supplies the DCT coefficients to a quantization circuit (quantizer) 2 that quantizes the DCT coefficient data with quantization steps selected as a function of the volume of data represented by the DCT transformation coefficients and supplies the quantized data to a scan converter circuit 3.
FIG. 2 illustrates the operation of the scan converter circuit 3. As shown in FIG. 2, the 64 DCT coefficients of each block supplied by the DCT circuit 2 correspond to various combinations of 8 horizontal spatial frequencies and 8 vertical spatial frequencies. The DCT coefficient having the lowest horizontal spatial frequency (0) and the lowest vertical spatial frequency (0), namely the DC coefficient, is represented by the region in the left uppermost corner. The remaining regions represent the 63 AC coefficients.
The scan converter circuit 3 arranges the 63 AC coefficients of each block into a sequence that starts from the AC coefficient representing the lowest horizontal and vertical spatial frequency and proceeds as a function of increasing horizontal and vertical spatial frequency, as represented by the zigzag pattern shown in FIG. 2. The scan converter circuit 3 supplies the DC coefficient and the sequence of AC coefficients to a variable length encoder circuit 4, shown in FIG. 1, which encodes the data using a variable length code.
The variable length encoder circuit 4 segregates the DC coefficient of each block from the sequence of AC coefficients and variable length encodes the AC and DC coefficients independently using a known arithmetic code such as a Huffman code.
FIG. 3 is a block diagram showing in greater detail the AC encoding portion of the variable length encoding circuit 4. As shown in FIG. 3, the AC coefficients arranged by scan converter circuit 3 are supplied to a zero decision circuit 41 which determines whether a respective AC coefficient has a zero value. The decision circuit 41 supplies AC coefficients having a zero value to run length counter 42 which counts successive zero value AC coefficients. The run length counter 42 supplies the count of successive zero value AC coefficients, known as a zero run length, to a two-dimensional Huffman encoder circuit 44. The zero run length has a maximum run of 15. If the count of successive zero value AC coefficients exceeds 15, the run length counter 42 supplies a flag ZRL to the encoder circuit 44 for every 16 successive zero value AC coefficients, followed by a zero run length representing the count of the remaining successive zero value AC coefficients.
Likewise, the decision circuit 41 delivers the AC coefficients having a non-zero value, known as effective AC coefficients, to a grouping circuit 43. The grouping circuit 43 groups the effective AC coefficients according to a predefined grouping table as shown, for example, in FIG. 4. The values of the AC coefficients are grouped in the table according to a respective group number which is the number of binary bits needed to represent the absolute value of the AC coefficient. The group number corresponding to each effective coefficient, as well as additional bits which represent the ordinal position of the AC coefficient within its respective group, are assigned to the coefficient. As an example, an AC coefficient having the value "-1" is assigned the group number 1 , as well as an additional bit which indicates that the value is the lower of the two values in the group. By contrast, an AC coefficient having a value "1" is also assigned the group number 1 but is assigned an additional bit indicating that the value is the greater value in the group. As a further example, an AC coefficient having the value "4" is assigned the group number 3 and three additional bits indicating that the value is the fifth value in the group.
The grouping circuit 43 supplies the respective group numbers for each effective AC coefficient to the two-dimensional Huffman encoder 44 which assigns a Huffman code value to each effective AC coefficient by referencing a previously generated two-dimensional Huffman coding table stored in coding table memory 45.
The two-dimensional Huffman coding table stored in coding table memory 45 is generated as a function of the frequency of occurrence of a respective combination of a group number and its immediately preceding zero run length as shown, for example, in FIG. 5. As an example of the generation of a Huffman coding table, FIG. 6A shows the iterative steps of forming a one-dimensional Huffman coding table by repeatedly determining the group numbers having the lowest frequencies of occurrence. In the first iteration, the least frequent group number, 5, is assigned a one-bit code of "zero" and the next least frequent group number, 7, is assigned a one-bit code of "one". The two group numbers are then combined to form a composite group number, {7, 5}, having the combined frequencies of the two group numbers, 6, and reordered to redetermine the two group numbers or composite group numbers having the least frequency of occurrence. The steps of assigning a one-bit code to the two group numbers and/or composite group numbers having the least frequencies of occurrence, combining the two numbers and then reordering the group numbers and composite group numbers are repeated until only one composite group number remains. Each of the original group numbers is thus assigned a sequence of "ones" or "zeros" shown in FIG. 6B, which represent the sequence by which each respective group value was combined into increasingly larger composite group numbers. FIG. 6C illustrates a tree structure showing how the group numbers are combined and by which the order of the group numbers as a function of frequency of occurrence can be reconstructed from the Huffman codes during subsequent decoding.
The two-dimensional Huffman coding table is generated in an analogous manner using predetermined frequency of occurrence values for each respective combination of the group number and the zero run length. The encoder 44 references the two-dimensional Huffman coding table and assigns Huffman code values as a function of a respective effective coefficient in the sequence of AC coefficients and its immediately preceding zero run length value. In a portion of a sequence of AC coefficients having values "0, 0, 1, 4", for example, the effective AC coefficient "1" corresponds to group number "1", as shown in FIG. 4, and is immediately preceded by a zero run length "2". The encoder 44 references the two-dimensional Huffman coding table shown in FIG. 5 and assigns the Huffman code value corresponding to group number "1" and zero run length "2" to the effective coefficient. Likewise, the effective AC coefficient "4" in this sequence corresponds to group number "3" and is immediately preceded by a zero run length "0" and the encoder circuit 44 assigns the Huffman code value corresponding to group number "3" and zero run length "0". If one or more ZRL flags precede the zero run length value, the encoder circuit 44 assigns the Huffman code value corresponding to the appropriate group number and zero run length "15".
The Huffman code assigned to each effective AC coefficient by the encoder circuit 44 and the corresponding respective additional bits generated by the grouping circuit 43 are combined and delivered to a formatting circuit 5 which formats the signals for subsequent transmission or recording on a recording medium via output terminal 12.
When the last AC coefficient of the block has a zero value, the variable length encoding circuit 4 appends an end of block indicator flag EOB to the sequence of Huffman codes and additional bits.
The DC coefficients are encoded by the variable length encoding circuit 4 by first determining the difference between the values of the DC coefficients of a pair of successive blocks of either luminance or chrominance signals. The encoding circuit 4 then groups the respective differences, known as difference values, by referencing a predefined grouping table similar to the table shown in FIG. 4, and assigns a group number and additional bits to each respective difference value. The respective group numbers are coded by referencing a previously generated one-dimensional Huffman coding table that is generated in the above-described manner, and the code data are delivered to the formatting circuit 5.
FIG. 7 illustrates a known arrangement for decoding variable length encoded signals that have been encoded in the above-described manner and that have been reproduced from a recording medium or transmitted and received. The variable length encoded signals are supplied to an input terminal 6 and delivered to a variable length code decoder 7. The variable length code decoder 7 decodes the variable length code signals by referencing a data table corresponding to the table shown in FIG. 5 and determines the group number of respective effective AC coefficients as well as the number of successive zero value coefficients that immediately precede the effective AC coefficient from the Huffman code value. The decoder 7 then determines the value of the effective AC coefficients from the group number and the additional bits. The variable length code decoder 7 also decodes the DC coefficients from the variable length code signals and supplies the DC coefficient and the AC coefficients for each block to a quantization decoder 8.
The quantization decoder 8 decodes the DC coefficient and the AC coefficients and supplies the quantization decoded coefficients to an inverse transform circuit 9. The inverse transform circuit 9 transforms each block of quantization decoded coefficients from the frequency domain into the time domain to form digital signals which are supplied to an output terminal 10 for subsequent reproduction.
The conventional encoding method described above has the drawback that the size of the coding table memory 45 limits the size of the two-dimensional Huffman coding table to coding values that correspond to zero run lengths of at most 15. Thus, the effective AC coefficients that are preceded by larger zero run lengths are not optimally encoded. Though the Huffman coding table can be expanded to include combinations representing larger zero run lengths, the size of the Huffman coding table can not be increased without significantly increasing the size of the memory.
Further, the same two-dimensional Huffman coding table is referenced regardless of whether the DCT coefficients represent luminance or chrominance signals. The coding table is not optimized to conform with the specific attributes of the luminance portion or the chrominance portion of the video image and, as a result, neither the variable length encoded signal representing the luminance signal or representing the chrominance signal is optimally compressed.
Also because variable length encoded signals are not optimally compressed, the maximum length of the signals is unnecessarily long and requires excessive memory.